| Legendre符号计算例题（二） | 您所在的位置：网站首页 › cipolla算法 例题 › Legendre符号计算例题（二） |
|
索引
前言
1. 计算 ( 7 11 ) \left( \frac{7}{11} \right) (117)。
2. 已知 563 563 563是素数，判断 x 2 ≡ 286 m o d 563 {
{x}^{2}}\equiv 286\text{ }\bmod 563 x2≡286 mod563是否有解。
3. 已知 103 103 103是素数，判断 x 2 ≡ 83 m o d 103 {
{x}^{2}}\equiv 83\text{ }\bmod 103 x2≡83 mod103是否有解。
4. 设 p p p是素数， x 2 ≡ 5 m o d p {
{x}^{2}}\equiv 5\text{ }\bmod p x2≡5 modp有解，求 p p p。
5. 设 p p p是素数， x 2 ≡ 7 m o d p {
{x}^{2}}\equiv 7\text{ }\bmod p x2≡7 modp有解，求 p p p。
前言
以下例题涉及的关于Legengre符号的计算性质和方法可以参见博文 《Legendre符号的定义和基本性质》 《Legendre符号的相关引理和部分计算性质的证明》 1. 计算 ( 7 11 ) \left( \frac{7}{11} \right) (117)。解法一 ( 7 11 ) ≡ ( − 1 ) 11 − 1 2 = − 1 m o d 11 ⇒ ( 7 11 ) = − 1 \left( \frac{7}{11} \right)\equiv { {\left( -1 \right)}^{\frac{11-1}{2}}}=-1\text{ }\bmod 11\text{ }\Rightarrow \text{ }\left( \frac{7}{11} \right)=-1 (117)≡(−1)211−1=−1 mod11 ⇒ (117)=−1 解法二 11 11 11是奇素数， gcd ( 7 , 11 ) = 1 \gcd \left( 7,11 \right)=1 gcd(7,11)=1。 11 − 1 2 = 5 , 11 2 = 5.5 \frac{11-1}{2}=5,\text{ }\frac{11}{2}=5.5 211−1=5, 211=5.5。有下表 x mod11 1 2 3 4 5 7 x mod11 7 ‾ 14 ≡ 3 21 ≡ 10 ‾ 28 ≡ 6 ‾ 35 ≡ 2 \begin{matrix} x\text{ mod11} & 1 & 2 & 3 & 4 & 5 \\ 7x\text{ mod11} & \underline{7} & 14\equiv 3 & 21\equiv \underline{10} & 28\equiv \underline{6} & 35\equiv 2 \\ \end{matrix} x mod117x mod1117214≡3321≡10428≡6535≡2 上表第二行中共有3个数 > 5.5 >5.5 >5.5，故 ( 7 11 ) = ( − 1 ) 3 = − 1 \left( \frac{7}{11} \right)={ {\left( -1 \right)}^{3}}=-1 (117)=(−1)3=−1 解法三 11 11 11是奇素数， gcd ( 7 , 11 ) = 1 \gcd \left( 7,11 \right)=1 gcd(7,11)=1， 2 ∣ 7 2\cancel{|}7 2∣ 7， 11 − 1 2 = 5 \frac{11-1}{2}=5 211−1=5，于是有 ( 7 11 ) = ( − 1 ) ∑ k = 1 5 [ 7 k 11 ] = ( − 1 ) [ 7 11 ] + [ 14 11 ] + [ 21 11 ] + [ 28 11 ] + [ 35 11 ] = ( − 1 ) 0 + 1 + 1 + 2 + 3 = ( − 1 ) 7 = − 1 \left( \frac{7}{11} \right)={ {\left( -1 \right)}^{\sum\limits_{k=1}^{5}{\left[ \frac{7k}{11} \right]}}}={ {\left( -1 \right)}^{\left[ \frac{7}{11} \right]+\left[ \frac{14}{11} \right]+\left[ \frac{21}{11} \right]+\left[ \frac{28}{11} \right]+\left[ \frac{35}{11} \right]}}={ {\left( -1 \right)}^{0+1+1+2+3}}={ {\left( -1 \right)}^{7}}=-1 (117)=(−1)k=1∑5[117k]=(−1)[117]+[1114]+[1121]+[1128]+[1135]=(−1)0+1+1+2+3=(−1)7=−1 2. 已知 563 563 563是素数，判断 x 2 ≡ 286 m o d 563 { {x}^{2}}\equiv 286\text{ }\bmod 563 x2≡286 mod563是否有解。解 由于 563 563 563是素数且是奇数， 5 |
| 今日新闻 |
| 推荐新闻 |
| 专题文章 |
| CopyRight 2018-2019 实验室设备网 版权所有 |